排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
1
2
| 输入：head = [4,2,1,3]
输出：[1,2,3,4]
|
示例 2：
1
2
| 输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
|
示例 3：
提示：
- 链表中节点的数目在范围 [0, 5 * 104] 内
- -105 <= Node.val <= 105
代码：
12%57%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| class Solution {
public ListNode sortList(ListNode head) {
List<ListNode> ls=new ArrayList<>();
if(head==null)return head;
ListNode t1=null;
ListNode t2=null;
while(head!=null)
{
t1=head;
head=head.next;
t2=head;
if(head==null)
{
ls.add(t1);
break;
}
else {
head=head.next;
if(t2.val< t1.val)
{
t1.next=null;
t2.next=t1;
ls.add(t2);
}else {
t2.next=null;
ls.add(t1);
}
}
}
while(ls.size()>=2)
{
ls.add(mergeTwoLists(ls.remove(0),ls.remove(0)));
}
return ls.get(0);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head=null;
ListNode ln=null;
ListNode temp;
for(;;)
{
if(l1==null||l2==null)break;
if(l1.val>=l2.val)
{
temp=new ListNode(l2.val);
if(head==null){ln=temp;head=ln;}
else {
ln.next=temp;
ln=ln.next;
}
l2=l2.next;
}
else{
temp=new ListNode(l1.val);
if(head==null){ln=temp;head=ln;}
else {
ln.next=temp;
ln=ln.next;
}
l1=l1.next;
}
}
if(head==null)
{
head=l1==null?l2:l1;
}
else {
ln.next=l1==null?l2:l1;
}
return head;
}
}
|
